class Solution300_2 {
    public static void main(String[] args) {
        int[] arr = {3,5,6,2,5,4,19,5,6,7,12} ;
        System.out.println(lengthOfLIS(arr));
    }

    public  static int lengthOfLIS(int[] nums) {
        int len = nums.length  ;
        int[] dp = new int[len] ;
        int num = Integer.MAX_VALUE ;
        for(int i=0 ; i < len ; i ++){
            dp[i] = num ;
        }
        int maxLen = 0 ;
        for(int i= 0 ; i < len ; i ++){
            int left = 0 ;
            int right = len-1 ;
            int cur = nums[i] ;
            while(left < right){
                int mid = left + (right-left)/2 ;
                if(dp[mid] != num && dp[mid] < cur){
                    left = mid+1 ;
                }else {
                    right = mid ;
                }
            }
            if(dp[left] == num){
                dp[left] = cur ;
                maxLen ++ ;
            }else{
                dp[left] = cur ;
            }
        }
        return maxLen ;
    }
}